/**
 * @Title: MergeSort.java
 * @Package com.adamjwh.sort.mergesort
 * @Description: 
 * @author adamjwh
 * @date 2018年6月25日
 * @version V1.0
 */
package com.adamjwh.sort.mergesort;

/**
 * @ClassName: MergeSort
 * @Description: 把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。
 * @author adamjwh
 * @date 2018年6月25日
 * @时间复杂度  最佳情况：T(n) = O(n)  最差情况：T(n) = O(nlogn)  平均情况：T(n) = O(nlogn)
 */
public class MergeSort {

	/**
	 * 
	 * @Title: merge
	 * @Description: 合并
	 * @param @param arr
	 * @param @param low
	 * @param @param mid
	 * @param @param high    参数
	 * @return void    返回类型
	 * @throws
	 */
	public static void merge(int[] arr, int low, int mid, int high) {
		int[] temp = new int[high-low+1];	//新数组
		int i = low;	//左指针
		int j = mid + 1;	//右指针
		int index = 0;	//临时变量，用于计算数组下标
		
		while(i<=mid && j<=high) {	//把较小的数先移到新数组中
			if(arr[i] < arr[j]) {
				temp[index++] = arr[i++];
			} else {
				temp[index++] = arr[j++];
			}
		}
		
		while(i <= mid) {	//把左边剩余数移入数组
			temp[index++] = arr[i++];
		}
		
		while(j <= high) {	//把右边剩余数移入数组
			temp[index++] = arr[j++];
		}
		
		for(int k=0; k<temp.length; k++) {	//把新数组中的数覆盖原数组
			arr[k+low] = temp[k];
		}
	}
	
	/**
	 * 
	 * @Title: mergeSort
	 * @Description: 合并排序
	 * @param @param arr
	 * @param @param low
	 * @param @param high    参数
	 * @return void    返回类型
	 * @throws
	 */
	public static void mergeSort(int[] arr, int low, int high) {
		int mid = ((high - low) >> 1) + low;
		
		if(low < high) {
			mergeSort(arr, low, mid);	//左边
			mergeSort(arr, mid+1, high);	//右边
			merge(arr, low, mid, high);	//左右合并
		}
	}
	
	/**
	 * 
	 * @Title: main
	 * @Description: 主函数——测试函数
	 * @param @param args    参数
	 * @return void    返回类型
	 * @throws
	 */
    public static void main(String[] args) {
        int a[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
        mergeSort(a, 0, a.length - 1);
        for(int arr : a) {
        	System.out.print(arr + " ");
        }
    }
	
}
